package puzzle.puzzleup2008;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * You will make a tour on a 5x5 chessboard, beginning from the upper left corner 
 * and ending at the bottom right corner.
 * 
 * �6�1 In each step of the tour, you can move to a square that is adjacent (right, 
 * left, up, down) to your current square.
 * 
 * �6�1 You will visit each square exactly once.
 * 
 * In how many different ways can this tour be done?
 * If the same question was asked for a 3x3 square, the answer would be 2.
 * 
 * @author Administrator
 *
 */
public class SquareTour {

	public static void main(String[] args) {
		
		List<String> result = process(7);
//		for (String r: result) {
//			System.out.println(r);
//		}
		int count = result.size();
		System.out.println(count);
	}

	static Map<Character, Integer> pos = new HashMap<Character, Integer>();
	static {
		pos.put('t', 0);
		pos.put('r', 1);
		pos.put('b', 2);
		pos.put('l', 3);
	}

	public static class Location {
		char type;	//'t':top, 'r':right, 'b':bottom, 'l':left, 's':start point, 'e':end point, 'm': temp location
		int x;
		int y;
		
		Location(char type, int x, int y) {
			this.type = type;
			this.x = x;
			this.y = y;
		}
		
		public String toString() {
			return type+"(" + x + "," + y +")"; 
		}
	}
	
	public static class Stack extends LinkedList<Location> {
		private static final long serialVersionUID = -2366743298522208112L;
		int maxIndex;

		public int find(int x, int y) {
			for (int i = 0; i < this.size(); i ++) {
				Location loc = this.get(i);
				if (loc.x == x && loc.y == y) {
					return i;
				}
			}
			return -1;
		}

		public String toString() {

			String str = "";
			int n = this.maxIndex;
			for (int y = 0; y < n; y ++) {
				for (int x = 0; x < n; x ++) {
					int p = find(x, y);
					if (p > -1) {
						str += p+"\t";
					} else {
						str += "*\t";
					}
				}
				str += "\n";
			}
			str += "\n";
			return str;
		}
		
		public boolean isAvailable(int x, int y) {
			return (x>-1 && x < this.maxIndex && y > -1 && y < this.maxIndex
					&& this.find(x, y) == -1);
		}
		
	}
	
	public static List<String> process(int n) {
		
		List<String> result = new ArrayList<String>();
		if (n == 1) {
			result.add("1");
			return result;
		} else if (n%2 == 0) {
			return result;
		}
		
		//initialize
		Location s = new Location('s', 0, 0);
		Location f = new Location('b', 0, 1);
		Stack stack = new Stack();
		stack.maxIndex = n;
		stack.addLast(s);
		stack.addLast(f);
		int size = n*n;
		while (!stack.isEmpty()) {
			if (stack.size() == size) {
				Location cur = stack.getLast();
				if (cur.x == n-1 && cur.y == n-1) {
					String r = stack.toString();
					if (result.contains(r)) {
						break;
					} else {
						result.add(r);
						stack.removeLast();
//						System.out.println(stack);
					}
				}
				traceback(stack);
			} else if (stack.size() < size) {
				Location cur = stack.getLast();
				Location next = next(stack, cur);
				if (next != null) {
					stack.add(next);
//					System.out.println(stack);
				} else {
					traceback(stack);
				}
			}
		}
		return result;
	}
	
	static Location next(Stack stack, Location cur) {
		
		if (stack.isAvailable(cur.x, cur.y-1)) {
			return new Location('t', cur.x, cur.y-1);
		} else if (stack.isAvailable(cur.x+1, cur.y)) {
			return new Location('r', cur.x+1, cur.y);
		} else if (stack.isAvailable(cur.x, cur.y+1)) {
			return new Location('b', cur.x, cur.y+1);
		} else if (stack.isAvailable(cur.x-1, cur.y)) {
			return new Location('l', cur.x-1, cur.y);
		} else {
			return null;
		}
	}
	
	static boolean change(Stack stack, Location cur) {
		
		if (cur.type == 's') {
			return true;
		}
		
		Location prev = previous(cur);
		int p = pos.get(cur.type);
		for (int i = p+1; i < 4; i ++) {
			if (i == 1) {
				if (stack.isAvailable(prev.x+1, prev.y)) {
					cur.type = 'r';
					cur.x = prev.x+1;
					cur.y = prev.y;
					return true;
				} else {
					continue;
				}
			} else if (i == 2) {
				if (stack.isAvailable(prev.x, prev.y+1)) {
					cur.type = 'b';
					cur.x = prev.x;
					cur.y = prev.y+1;
					return true;
				} else {
					continue;
				}
			} else if (i == 3) {
				if (stack.isAvailable(prev.x-1, prev.y)) {
					cur.type = 'l';
					cur.x = prev.x-1;
					cur.y = prev.y;
					return true;
				} else {
					continue;
				}
			}
		}
		return false;
	}
	
	static Location previous(Location cur) {

		if (cur.type == 't') {
			return new Location('m', cur.x, cur.y+1);
		} else if (cur.type == 'r') {
			return new Location('m', cur.x-1, cur.y);
		} else if (cur.type == 'b') {
			return new Location('m', cur.x, cur.y-1);
		} else if (cur.type == 'l') {
			return new Location('m', cur.x+1, cur.y);
		} else {
			return null;
		}
	}
	
	public static void traceback(Stack stack) {
		
		Location cur = stack.getLast();
		while (!change(stack, cur)) {
			if (!stack.isEmpty()) {
				stack.removeLast();
//				System.out.println("---traceback:---");
//				System.out.println(stack);
				cur = stack.getLast();
			} else {
				break;
			}
		}
	}
}
